csgcfandomcom-20200213-history
Csgc Wiki
Solutions for the Algorithms course. The source code can be uploded to http://ideone.com, where we can compile and run all programs online (more than 40 languages supported). Problem 1.1.1. Sum from Sorted Arrays http://ideone.com/ePUaa Index i goes down from n-1 to 0, and index j goes up from 0 to n-1. The sum ai + bj is compared to x, and either i is decremented, or j is incremented. Problem 1.1.2. Comparator Network: 2 Smallest Problem 1.1.3. Search with a "Clue" See James's solutions Problem 1.1.4. Sorting Bitonic Arrays HW2, Problem 7. Firstly, find the index i, it takes at most (n − 1) comparisons. At the same time, we also determine, whether Ai is the smallest or the largest element of the array. Then, merge the left and the right halves of the array (they are already sorted). It will take at most (n − 2) comparisons more. In total, in the worst case, we need 2n − 3 = O(n) comparisons. Problem 1.1.5. Trinary Search Problem 1.1.6. Nuts and Bolts Part 1: '''for i=1 to n '''Part 2: Assume you have n nuts and n bolts in some order. For example, take n = 5. Then the two lists are b4,b3,b1,b5,b2 and n1,n5,n4,n2,n3. Lets say b5>b4>...>b1 and n5>n4>...>n1. We can start comparing the lists in the following way: compare (b4,n1). Since b4 is too big for n1, throw away n1. Then compare (b4,n5). Since b4 < n5, throw away b4. Then (b3, n5) -> throw away b3. Similarly, (b1,n5), then (b5,n5). At this point we make a note that they are equal. Drop the bolt (or the nut - but decide on this scheme before starting scanning). Next compare (b2,n5), b2 is too small and the set of bolts has been exhausted. The last recorded equal pair is the largest. This has a maximum of 2n - 2 comparisons (one comparison tells us whether it's <, =, or >). Problem 1.1.7. Partitioning from multiple sorted arrays O(log(n)) algorithm based on binary search: http://ideone.com/41tHc. Search for a index i s.t. all elements a0, a1 ... ai, b0, b1, bn-2-i are in the set of n smallest elements, + be careful on the boundary when i=0. The number of comparisons in the worst case = ceil(log n) Problem 1.1.8. Matrix with some ordering O(n) algorithm, (4n-2) in the worst case: (2n-1) equality comparisons, and (2n-1) less-than comparisons. http://ideone.com/ZWYBX Probably, it can be done more efficiently, without that many equality comparisons. Also, if x is in the matrix than (4n-3) comparisons at most. The idea is to walk from the top-right corner of the matrix to its bottom-left corner, trying to find x: if mi,j < x then go down (i.e. i = i+1), otherwise if mi,j > x then go to the left (i.e. j = j-1) Problem 1.1.10. Overlapping Sorted Arrays Part(a). I know one inefficinet search with 2(2n-1) comparisons in the worst case. Simply scan the arrays simultaneously. However, if we can abuse subtraction and multiplication, there is a way to find an element that is present in both arrays in 2 \lceil\log_2 n\rceil comparisons. See http://ideone.com/ONW26 Part(b). The same cheating abusing multiplication and subtraction let us solve the problem with 2 \lceil\log_2 n\rceil comparisons However, I believe that Professor does not expect such approach, because it does not use the fact that numbers in the array are ordered. Problem 1.1.11. Using Ternary Comparison Part 1. Find the largest. At every comparison we can drop two small elements each time. It gives \lfloor n/2 \rfloor comparisons. Or, if n = 3^k , n is always odd, so we get (n-1)/2 comparisons in this case. Exactly the same answer can be obtained, if we consider the parallel method of finding the largest (see lecture notes). Note that if n=27, in the first parallel round we do 9 comparisons, then 3, then 1. 9+3+1 in total. The general formula: \sum_{i=0}^{\log_3 n - 1} 3^i = \dfrac{1-3^{\log_3 n}}{1-3} = \dfrac{1-n}{-2} = \dfrac{n-1}{2} . The same answer, indeed. Part 2. Find the largest and the smallest. Ok, here we again follow the parallel solution. If n=27, on the first round we compare all elements in 9 comparisons. But after that we search for the largerst within the group of 9 largest elements, and search for the smallest in the group of the 9 smallest elements. In total, it takes 9 + (3+1) + (3+1) comparisons. The general formula: \dfrac{n}{3} + 2 \Big( \sum_{i=0}^{(\log_3 n) - 2} 3^i \Big) = \dfrac{n}{3} + 2 \dfrac{1-3^{(\log_3 n) - 1}}{1-3} = \dfrac{n}{3} + 2 \dfrac{1-n/3}{1-3} = \dfrac{n}{3} + \dfrac{n}{3} - 1 = \dfrac{2}{3} n - 1 . Generalize it further? If we use comparison of arity t: \dfrac{n}{t} + 2 \Big( \sum_{i=0}^{(\log_t n) - 2} t^i \Big) = \dfrac{n}{t} + 2 \dfrac{1-t^{(\log_t n) - 1}}{1-t} = \dfrac{n}{t} + 2 \dfrac{1-n/t}{1-t} = \dfrac{nt + n - 2t}{t(t-1)} . Check, for t=2 we need \dfrac{3}{2}n-2 comparisons, and for t=3 : \dfrac{2}{3}n - 1 . Part 3. There were \lceil \log_3 n \rceil comparisons with the largest element. We are interested in those elements that were second in the results of these comparisons. It takes \lceil \log_3 n \rceil - 1 to find the largest among them. It means that to find both the largest and the second largest takes \dfrac{n-1}{2} + \lceil \log_3 n \rceil - 1 . Category:Browse